Internet search engines widely use online keyword auctions to sell advertising spaces on search results pages. In a typical online keyword auction, participating advertisers bid on certain terms for their advertisements. Each term comprises one or more keywords. When a query submitted to an Internet search engine partially or completely matches a bidded term, the advertisements from participating advertisers may be listed along with the search results of the query. The advertisements are usually displayed in certain advertising spaces on a Web page. When the Web page is a search results page of a query, the advertising spaces are typically on the top, bottom, left, or right hand side of the search results page. The advertisements are usually ordered by the amount of the bid and the relevance of the advertisement to the query. The advertisers are only charged when the advertisement is clicked on, presumably by a human being. This type of advertising service provided by the Internet search engines is often referred to as Pay-Per-Click (PPC) advertising or Sponsored Search, which is different from the traditional impression based accounting for advertisements. Traditionally, advertisers are charged by the number of impressions an advertisement is shown to a target audience. PPC advertising gives more visibility to advertisers as to who may be interested in the advertisements and who may ultimately enter a transaction to purchase the advertised products or services. Therefore, PPC advertisers are willing to bid on certain keywords in an online auction to more precisely target advertising audiences. As a result, online keyword auctions have generated significant revenue for the Internet search engines.
The number of online keyword auctions conducted on a daily basis at the major Internet search engines is on the order of hundreds of millions. The revenue generated by the auctions may reach tens of billions of dollars per year for the Internet search engines. Consequently, the online keyword auction has attracted considerable attention from practitioners as well as academics. One research area involves designing an optimal auction mechanism and finding optimal market reserve prices for the keywords in an online auction. A market reserve price is a minimum bid for a bidded term comprising one or more keywords. There is no sale if the bids are below the market reserve price. Most auction mechanism designs make certain assumptions about bidders for the keywords. In general, assumptions are often made about the value distribution and the rationality of the bidders. The value distribution refers to a range of values a bidder has for the bidded term in the auctions. The bidder submits higher and higher bids to compete for the bidded term until the current bid is over the bidder's value range for the bidded term. The rationality refers to the bidders' rationality in a bidding process. In empirical studies, one particular form of bidder irrationality called loss aversion has been observed. A bidder considers that it is “losing” an item when it was the high bidder at one time during the bidding process. Such a loss averse bidder may bid more aggressively after having had the highest bid at any point in the bidding process but was later outbidded by another bidder.
The goal of an auctioneer of online keyword auctions is to find the auction parameters that result in a maximum value of an objective function for the keyword auctions. The objective function often is the expected revenue from the keyword auctions. In order to mathematically model the online keyword auctions, bidders and their behaviors often have to be simulated based on recorded data from past auctions of the same or similar keywords. The behavior of bidders, however, differs for different keywords at different times. To adapt to the ever changing characteristics of the bidders, auctioneers often use adaptive learning algorithms to revise the auction parameters such as the market reserve prices of the keywords in response to observed results of previous auctions. The learning algorithms themselves are often parameterized. The optimal values of the learning parameters of these algorithms will have to be determined so that the learning algorithms may be able to quickly find the optimal auction parameters for the online keyword auctions.